package leetcode93复原IP地址;

import java.util.ArrayList;
import java.util.List;

/**
 * @author wtcode
 * @date 2021/3/22 - 21:50
 */
public class Solution2 {
    private static final int SEG_SIZE = 4;
    List<String> res = new ArrayList<>();
    int[] segments = new int[SEG_SIZE];

    public List<String> restoreIpAddresses(String s) {
        segments = new int[SEG_SIZE];
        dfs(s,0,0);
        return res;

    }

    private void dfs(String s, int segId, int segStart) {
        // 如果成功遍历到了结尾，并且
        if(segStart == s.length()){
            if(segId == SEG_SIZE){
                StringBuffer ipadd = new StringBuffer();
                for(int i = 0 ; i < SEG_SIZE ;i++){
                    ipadd.append(segments[i]);
                    if(i != SEG_SIZE - 1){
                        ipadd.append(".");
                    }
                }
                res.add(ipadd.toString());
            }
            return;
        }

        if(segStart == s.length()){
            return;
        }

        if(s.charAt(segStart) == '0'){
            segments[segId] = 0;
            dfs(s,segId+1,segStart+1);
        }

        int sum = 0;
        for(int segEnd = 0 ; segEnd < s.length() ; segEnd++){
            sum = sum * 10 + (s.charAt(segEnd)-'0');
            if(sum > 0 && sum <= 0xFF){
                segments[segId] = sum;
                dfs(s,segId+1,segEnd+1);

            }else {
                break;
            }
        }


    }


}
